#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
struct Node {
     int val;
     struct Node *next;
     struct Node *random;
 };
 
typedef struct Node Node;
Node* Newnode(int x) {
    Node* newnode = (Node*)malloc(sizeof(struct Node));
    if (newnode == NULL) {
        perror("newnode::malloc");
        return 0;
    }
    newnode->val = x;
    newnode->next = NULL;
    newnode->random = NULL;
    return newnode;
}
struct Node* copyRandomList(struct Node* head) {
    Node* cur = head;
    while (cur)
    {
        Node* node = Newnode(cur->val);
        node->next = cur->next;
        cur->next = node;
        cur = node->next;
    }
    cur = head;
    while (cur)
    {
        Node* copy = cur->next;
        if (cur->random != NULL)
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    cur = head;
    Node* phead = NULL;
    Node* ptail = NULL;
    while (cur)
    {
        Node* copy = cur->next;
        Node* next = copy->next;
        if (phead == NULL)
        {
            phead = ptail = copy;
        }
        else
        {
            ptail->next = copy;
            ptail = ptail->next;
        }
        cur = next;
    }
    return phead;
}
int main()
{
	return 0;
}